<html>

<head>
<title>6.863 Project - Eric Lieberman and Mike Lin</title>
<link rel="StyleSheet" href="style.css">

<script>

function writeFigure(num, image, caption) {

  document.write('<div align="center"><table border=0 width=600>');

  document.write('<tr><td><div align="center">');
  document.write('<a name="fig' + num + '">');
  document.write('<img src="' + image + '"></a></div></td></tr>');
  
  document.write('<tr><td><div align="center">');
  
  document.write('Figure ' + num + ': ');
  document.write(caption + '</div></td></tr>');
  
  document.write('</table></div>');
}

</script>


</head>

<body bgcolor="white">
<div align="center">
<table border=0 width=800 class="doc"><tr><td class="header">

<div align="center">
<font size=6><b>Natural Language Conversion to SQL</b></font><br>
<font size=4>6.863 Project</font><br>
<font size=4>Eric Lieberman and Mike Lin</font><br>
<font size=3>5/22/06</font>
</div>
</td></tr>
<tr><td class="body">
<p>
<hr>

<h2>Introduction</h2>

Interpreting and storing data whose input form is a natural language
is a difficult task.  Lab 3 had a primitive fact storage mechanism,
but we were interested in extending that to a true database system.
Therefore, we decided to convert the mechanism from Lab 3 to instead
use a common SQL database, and we have provided a web front end for
exploring this database.

<p>

<font size=4><b>
<a href="../index.py">Please click here to test our prototype.</a>
</b></font>

<h2>Design</h2>

We support most of the types of sentences that Lab 3 is able to parse.
We do this by converting the natural language into its SQL
counterpart.  For example, a statement such as "John kissed Mary"
might get translated into a SQL command like "INSERT INTO Event
(agent, patient) VALUES ('John', 'Mary')".  We can represent yes or no
questions with "SELECT" statements that check to see if a count is
correct.  We can also represent "wh"-questions by simple select
statements as well.
<p>

Implementing the basics of this system was very simple, but as we
tried to support more and more features it quickly became more
complex.  Currently, our database system uses three separate tables:

<ul>
  <li>Events - events that happen in the world.</li>
  <li>Objects - objects that exist in the world.</li>
  <li>Modifiers - modifiers on objects that exist in the world.</li>
</ul>

By using this split of information, we can represent many complicated
sentences; however, it may require multiple SQL statements to
correctly access or insert the information.  For example, even such a
simple sentence as

<pre>
John hates the yellow cats
</pre>

requires these SQL statements:

<pre>
SELECT id FROM Object WHERE name='John'
SELECT CASE WHEN COUNT(*) = 1 THEN Object.id ELSE NULL END FROM
  Object, Mod WHERE Object.type='cats' AND Object.definite = '+' AND
  Mod.target = Object.id AND (Mod.mod = 'yellow') 
INSERT INTO Event VALUES ('hate',61,62,NULL,'present')
</pre>


<h3>Question and Answer</h3> 

Our system can also answer questions using SQL "SELECT" statements:

<pre>
What does John hate
</pre>

<pre>
SELECT id FROM Object WHERE name='john'
SELECT id,name,type,definite FROM Event, Object WHERE action='hate'
  AND tense='present' AND agent=63 AND Object.id = patient
</pre>

<h3>Multiple adjectives</h3>
Our system allows the user to use multiple adjectives, and each gets
its own line in the database:
<pre>
John likes smart red cats
</pre>
is converted to
<pre>
SELECT id FROM Object WHERE name='John'
INSERT INTO Object(name,type,definite) VALUES ('John',NULL,NULL)
SELECT CASE WHEN COUNT(*) = 2 THEN Object.id ELSE NULL END FROM
  Object, Mod WHERE Object.type='cats' AND Object.definite = '+' AND
  Mod.target = Object.id AND (Mod.mod = 'smart' OR Mod.mod = 'red')
INSERT INTO Object(name,type,definite) VALUES (NULL,'cats','+')
INSERT INTO Mod (mod,target) VALUES ('smart',64),('red',64)
INSERT INTO Event VALUES ('like',63,64,NULL,'present')
</pre>

Objects with different sets of adjectives are distinct in our system.
For example, "the yellow dog" and "the blue dog" are represented as
different objects.

<h3>Adjective transpose</h3>
Unlike the original lab 3, our system allows the user to transpose
adjectives in any way they want, so the following two sentences are
logically equivalent:
<pre>
John likes big yellow cats
John likes yellow big cats
</pre>


<h3>Definite answers to indefinite questions</h3>

Questions that ask for indefinite answers are allowed to be answered
by definite answers.  For example:

<pre>
John likes the dog
Does John like a dog
</pre>

In our system the answer is correctly "Yes" even though a naive system
that simply compared the definite characteristic would not succeed.

<h3>Multiple answers to wh-questions</h3> 

With our SQL system, if there are many objects that correctly answer a
single wh-question, we are able to return all of the answers to them.
Take for example the following sequence of statements:

<pre>
John likes Mary
Fido likes Mary

Who likes Mary
</pre>

Our system correctly responds with "John and Fido."



<h2>Implementation</h2>

Our system is implemented in python, and we have essentially replaced
the data storage element of lab 3 with our own system.  We also wrote
the web-based user interface for the system.  

<p>

The greatest challenge in implementing this system was converting
complicated natural language statements into SQL.  Initially, we had
hoped that it would be simple, but when we had to start adding
multiple databases the complexity grew quickly.  

<p>

In particular, when we were implementing modifiers, we determined that
we wanted to be able to ask questions like "Does John like the rabid
yellow dog".  This question requires finding a dog that is yellow as
well as rabid, but we do not want to limit it to that order.  To do
this, we could have used a combined select to first find the yellow
dogs, then find the rabid ones from among them.  This was complicated,
however, so instead we search for all of the modifiers of that dog
that are either yellow or rabid.  Then, we count to make sure that the
amount found is equal to the number of modifiers.

For example, for a "rabid yellow dog" we search for modifiers of a
particular dog where the row count of modifiers which are yellow or
rabid equals 2.  Here's the SQL:

<pre>
SELECT CASE WHEN COUNT(*) = 2 THEN Object.id ELSE NULL END FROM
  Object, Mod WHERE Object.type='dog' AND Object.definite = '+' AND
  Mod.target = Object.id AND (Mod.mod = 'rabid' OR Mod.mod = 'yellow')
</pre>


<p>

We also implemented a system where a system output is translated back
into natural language for display to the user.  You can see this in
action in the "Final Answer" portion of the user interface, or if you
click the "List Objects" button.


<h2>Future Work</h2>

In this section we will discuss some ideas we considered implementing,
and how one could extend our system to implement them.

<h3>More parts of speech</h3> 

The system could easily be extended to add other parts of speech.  One
could add adverbs to verb phrases, and then use those adverbs to reply
to "how" questions.  These adverbs would have to be stored in their
own adverb table in a very similar manner to the way modifiers are
currently stored.  For example, "John walked quickly" would store
"quickly" in the adverb table with an id corresponding to the event
that John walked.  Then the system could respond to the question "How
did John walk" with "quickly."

<p>

We could also incorporate locations in much the same way.  "John hid
under the desk" could be stored as an event of John hiding with the
location "under the desk".  The location could be stored as a
preposition plus the object that it was applied to; in this case,
"under" and "the desk".


<h3>Transactions</h3>

One of the strengths of a full database system is the idea of
transactions, where a set of statements is made atomic.  This feature
would give us a great deal of power to undo and redo statements that
the user makes.  It would probably be very easy to integrate; one
could simply start with a "begin transaction", run the sql, and then
"commit" at the end.


<h3>Translation</h3>

Now that we have the information stored in our database, we should
have a mechanism to convert that information back into a natural
language.  We currently have a method for doing this for objects, but
we would like to extend it to the entire system.  This would involve a
closer interaction with pykimmo which would allow us to translate
things like "kiss[past +]" directly into the correct form "kissed".


<h2>Example Sentences</h2>



Here is a list of example sentences you could try:

<pre>
John kissed Mary
Who did John kiss
Did John kiss Mary

Mary hates the yellow dog
John hates the yellow dog
Who hates the yellow dog
What does Mary hate

John killed the smart rabid werewolf
Did John kill the werewolf
Did John kill the rabid smart werewolf

John likes the dog
Does John like a dog
</pre>

<p>

If you would like the code of our prototype, it is bundled <a
href="../source.tar.gz">here.</a>








</td></tr></table>
</body>


</html>
